Turing machine

машина Тьюринга

гипотетический вычислитель, который предложил английский математик Алан Тьюринг (Alan Turing) в 1936 г. как инструмент для изучения сложности алгоритмов. Целью Тьюринга было описать границу между тем, что вычислительная машина может делать, и тем, что ей не под силу. Машина Тьюринга состоит из блока управления, считывающей и записывающей головки и в обе стороны бесконечной длины ленты, разделённую на ячейки, каждая из которых может содержать произвольный символ некоторого конечного множества, называемого алфавитом данной машины. Его элементы называются символами, или буквами, а конечные последовательности букв - словами. Вычисления состоят из последовательности шагов, задаваемых программой блоку управления. Ячейка, находящаяся под считывающей головкой, называется текущей. Каждый шаг может включать в себя считывание символа в текущей ячейке, запись в неё символа, возможное перемещение головки в соседнюю ячейку слева или справа, смену состояния и остановку. Программа представляет собой таблицу переходов, которая определяет поведение машины в зависимости от состояния и символа в текущей ячейке. Таблица переходов для каждой пары текущее состояние, текущий символ задаёт тройку значений новое состояние, новый символ, сдвиг. Вычисления начинаются в специальном состоянии, называемом стартовым (initial state), и заканчиваются в состоянии, называемом остановом. Кроме наличия бесконечной памяти, современные процессоры очень похожи на машину Тьюринга

см. тж. abstract computer, automata theory, Church thesis, computable function, lambda calculus